from typing import *


class Solution:

    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:

        class UnionFind():

            def __init__(self, size: int) -> None:
                self.p = [i for i in range(size)]
                self.cnts = [1] * size
                self.size = size

            def find(self, a):
                if self.p[a] != a:
                    self.p[a] = self.find(self.p[a])
                return self.p[a]

            def union(self, a: int, b: int):
                A, B = self.find(a), self.find(b)
                if A != B:
                    self.p[B] = A
                    self.cnts[A] += self.cnts[B]
                    self.cnts[B] = 0
                    self.size -= 1

            def isSameSet(self, a: int, b: int) -> bool:
                return self.find(a) == self.find(b)

        n = 0
        for a, b in edges:
            n = max(n, a)
            n = max(n, b)
        uf = UnionFind(n + 1)
        for a, b in edges:
            if uf.isSameSet(a, b):
                return [a, b]
            uf.union(a, b)
